This invention relates generally to resource allocation and, more particularly, relates to the allocation of memory among one or more network communication devices.
As the complexity of modern computer software increases, ever greater demands are placed on the computer hardware on which this software is run. One such demand is the need for ever increasing Random Access Memory (RAM) space. The computer""s memory provides the necessary space for the software to use while it is running on the computer. The memory is used by the computer to store the data required by the software. Varying software programs require varying amounts of memory, and even the same software program may require different amounts of memory at different times during its operational cycle. Software and hardware manufacturers have come up with a number of different schemes to allow computer hardware with limited memory to run software of increasing complexity. Once such scheme is known as xe2x80x9cvirtual memoryxe2x80x9d, and operates by moving data which has not been recently accessed from the limited memory storage to more available hard drive space. One difficulty with such a system is the inefficiency introduced by the transfer of data to and from memory as it is needed by a computer program. Another difficulty is limited speed with which information can be written to and read from a hard drive as compared to the read/write speed of a computer""s memory.
To alleviate the need to resort to inefficient schemes such as virtual memory, computer software and hardware manufacturers have attempted to make more efficient use of the existing memory. Because the need for memory can be transient, a dynamic memory allocation scheme can allocate memory from software which does not currently require it to software currently in need of it. The difficulty, however, with such a dynamic memory allocation scheme is selecting an efficient set of rules for granting memory. Should the memory be granted too freely, all of the available memory will be quickly used up, leaving none for other software packages to perform even the most simple of tasks. Should the memory be granted too restrictively, the advantage of a dynamic memory allocation scheme is lost since memory requests will be denied too often, resulting in poor performance.
Dynamic allocation of memory is generally most helpful when the memory requirements are continually changing. For example, network interface devices, such as a network interface card (NIC), require a constantly changing amount of memory to use as a buffer to temporarily store the packets they are sending and receiving. A packet to be sent across a network is placed in the buffer of a NIC. The NIC then reads the data from the buffer and sends it across the network, and the buffer is subsequently cleared to make room for the next packet to be sent. Generally, there is sufficient buffer space to store more than one packet. This allows the software sending the packets to continue sending packets at a steady rate, even if the NIC is not able to always transmit the packets immediately. Should the network become congested, the NIC will transmit the packets at a slower rate, and the packets being sent by the software will be queued in the buffer for transmission at a later time when the network congestion is resolved, and the NIC can resume sending the packets at an optimal rate. When the NIC does resume sending the packets at an optimal rate, it may be able to send the packets faster than they are being added to the buffer by the software, eventually clearing the buffer of all queued packets.
Other subsystems of a modern personal computer likewise have continually changing memory requirements. For example, printer drivers are similar to NICs in their need for an ever changing amount of buffer storage. Given such transient memory requirements, a dynamic memory allocation scheme can increase the efficiency of the memory usage, increasing the amount of memory given to a requester under certain circumstances. However, as stated above, the difficulty with such a dynamic memory allocation scheme is selecting an efficient set of rules for granting memory. It is inefficient to merely grant memory to a first requestor whenever available memory exists, as such a scheme would allow the first requestor to use up all of the available memory, leaving none for a second requestor to use even if it only needed a minimal amount. Conversely, a scheme which would reserve extra memory for the second requester will also be inefficient, because the second requestor may never need the space. It is difficult to properly balance the need to freely grant a memory request with the need to conserve resources for future requests from other sources.
Accordingly, the present invention provides a method for dynamically allocating resources among different requesters.
The present invention also provides a method for determining when to allocate a resource to a requester.
The present invention additionally provides a system which can grant a disproportionately large amount of resources to a single requestor while maintaining resources in reserve to assure fairness among many requesters.
The invention solves the above difficulties of memory allocation by providing a novel dynamic resource allocation scheme which allows one requestor to be granted a significant part of the available free resources, while maintaining a sufficient safety buffer to satisfy other requestors over a period of time. While the present invention can solve the above memory allocation problems, it is equally useful with any shared resource, such as processor cycles, and the like. Because of the transient nature of some resource requirements, the invention can meet disproportionately large resource requests of limited duration while maintaining overall fairness in the amount of resources provided to each requestor. By maintaining a buffer, the system can temporarily satisfy requests from other requestors. When such other requests increase, the invention can deny continuing requests from a requestor who has been granted too many resources and thereby diminish that requestor""s resource consumption and increase the resources available to satisfy the other requests. Thus, the invention minimizes the number of times a request for resources must be denied and thereby facilitates the operation of a software in an environment of limited resources. By minimizing the number of times a request for resources must be denied, the present invention can also increase the network throughput and increases the stability of the entire computer system.
The dynamic resource allocation scheme contemplated by the present invention is based on two simple rules. Initially, the available resources are mathematically divided among the requesters. Each requestor""s share is known as that requestor""s xe2x80x9cfair sharexe2x80x9d. Furthermore, a certain amount of resources, or a percentage of the total resources, are set aside as a xe2x80x9csafety bufferxe2x80x9d. The size of the safety buffer can vary from application to application, depending, among other things, on the nature of the resource requirements of the particular application. The first rule of the scheme contemplated by the present invention is that the requester is granted resources so long as there are resources available and the requestor has not consumed more than its fair share. The second rule is that the requestor is granted resources, even if it has exceeded its fair share, so long as the safety buffer remains unused.
The interaction of these two rules can best be analyzed temporally. Consider the situation where one requestor initially needs a lot of resources. Resources will be granted to it until its fair share is used up. After that, the first requestor will continue to be granted resources, should it need them, until all available resources, minus the safety buffer, are used. Now consider a second requestor which also needs resources. Initially it will be granted the resources from the safety buffer. As the second requestor uses up resources, the safely buffer shrinks, and additional requests from the first requestor will be denied, as some of the safety buffer is now used. As the first requestor frees some of its initial resources, and its requests for additional resources are denied, the total resources used by the first requestor will decline. Eventually, the system will reach a steady-state where each requestor is consuming at least their fair share of resources, and the safety buffer remains in case a third requester needs resources.
As can be seen, the scheme contemplated by the invention allows for flexibility in granting resources to a requestor, while maintaining the ability to satisfy additional requesters. The scheme may thereby increase the throughput of the network, decrease number of packets dropped, and otherwise facilitate the operation of a computing device with limited resources. Additional features and advantages of the invention will be made apparent from the following detailed description of illustrative embodiments that proceeds with reference to the accompanying figures.